﻿/*
题目: 买卖股票的最佳时机 III
 
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 最多进行两次交易
#define HAS_1   0
#define SELL_1  1
#define HAS_2   2
#define SELL_2  3

    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(4, vector<int>(prices.size(), 0));
        std::fill(dp[HAS_2].begin(), dp[HAS_2].end(), INT_MIN);

        dp[HAS_1][0] = -prices[0];

        for (int i = 1; i < prices.size(); i++) {
            dp[HAS_1][i] = max(dp[HAS_1][i - 1], -prices[i]);      // 选择保留，或者买更小的
            dp[SELL_1][i] = max(dp[HAS_1][i - 1] + prices[i], dp[SELL_1][i - 1]);          // 选择卖出第一个股票

            if (dp[SELL_1][i - 1] > 0) {
                dp[HAS_2][i] = max(dp[HAS_2][i - 1], dp[SELL_1][i - 1] - prices[i]);
                dp[SELL_2][i] = max(dp[SELL_2][i - 1], dp[HAS_2][i - 1] + prices[i]);
            }
        }

        return max(dp[SELL_1][prices.size() - 1], dp[SELL_2][prices.size() - 1]);
    }
};